import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-10-26
 * Time: 11:55
 */
public class test2 {
    class Leaf{
        int val;
        List<Integer> path;
        Leaf(int val,List<Integer> path){
            this.val = val;
            this.path = path;
        }
    }


    public int getDis (TreeNode root) {
        // write code here
        if(root==null){
            return 0;
        }
        List<Leaf> leaves = new ArrayList<>();
        dfs(root,new ArrayList<>(),leaves);
        if(leaves.size()<2){
            return 0;
        }

        Leaf maxLeaf = leaves.get(0);
        Leaf minLeaf = leaves.get(0);
        for(Leaf leaf:leaves){
            if(leaf.val>maxLeaf.val){
                maxLeaf = leaf;
            }
            if(leaf.val<minLeaf.val){
                minLeaf = leaf;
            }
        }
        int distance = 0;
        int i = 0;
        while(i<maxLeaf.path.size() && i<minLeaf.path.size() && maxLeaf.path.get(i)==minLeaf.path.get(i)){
            i++;
        }
        distance = (maxLeaf.path.size()-i) + (minLeaf.path.size()-i);
        return distance;
    }


    private void dfs(TreeNode node ,List<Integer> path,List<Leaf> leaves){
        if(node==null){
            return ;
        }
        path.add(node.val);
        if(node.left==null && node.right==null){
            leaves.add(new Leaf(node.val,new ArrayList<>(path)));
        }else{
            dfs(node.left,path,leaves);
            dfs(node.right,path,leaves);
        }
        path.remove(path.size()-1);
    }


    public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
}
